import java.util.HashSet;
import java.util.Set;

public class Solution930 {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int res = 0;
        int n = Math.max(goal+1,2);
        int[] last = new int[n];
        last[nums[0]] = 1;
        res+=last[goal];
        for (int i = 1; i < nums.length; i++) {
            int tmpNum = nums[i];
            int[] tmp = new int[n];
            for (int j = 0; j < last.length; j++) {
                int tmpLoc = j+tmpNum;
                if(tmpLoc<n){
                    tmp[tmpLoc] = last[j];
                }
            }
            tmp[tmpNum]++;
            res+=tmp[goal];
            last = tmp;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution930 s=new Solution930();
        System.out.println(s.numSubarraysWithSum(new int[]{1,0,1,0,1},2));
    }
}
